W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Każdy niepusty ciąg, którego elementami są małe litery i , a także ciąg pusty nazywamy ab-słowem. Jeżeli jest ab-słowem, a takimi dowolnymi liczbami całkowitymi, że , to przez będziemy oznaczali podsłowo składające się z kolejnych liter . Powiemy, że ab-słowo jest ładnie zbudowane, jeżeli zawiera tyle samo liter , co i dla każdego podsłowo zawiera co najmniej tyle samo liter , co liter .
Podamy teraz indukcyjną definicję podobieństwa ładnie zbudowanych ab-słów:
Stopniem zróżnicowania niepustego zbioru ładnie zbudowanych ab-słów nazywamy największą liczbę ab-słów, które można wybrać z tak, żeby żadne dwa wybrane słowa nie były do siebie podobne.
Napisz program, który
Na standardowym wejściu znajdą się:
W pierwszym i jedynym wierszu standardowego wyjścia należy zapisać jedną liczbę całkowitą — stopień zróżnicowania .
Dla danych wejściowych:
3 aabaabbbab abababaabb abaaabbabb
poprawną odpowiedzią jest:
2
Autor zadania: Krzysztof Diks.